package DataStructrue;

import java.util.ArrayDeque;
import java.util.Deque;

//单调栈,单调队列
public class Monotone {

    //寻找左右最近的>a[i]或>=a[i]的目标索引
    public static int[][] nearGreater(long[] arr){
        int n=arr.length;
        int[][] lr=new int[n][2];
        for (int i = 0; i < n; i++) {
            lr[i][0]=-1;lr[i][1]=n;
        }
        Deque<Integer> s=new ArrayDeque<>();//递减栈
        for (int i = 0; i < n; i++) {
            //如果a[i]较大,则栈中<a[i]的元素的右目标值即为a[i],这些元素出栈
            while(!s.isEmpty()&&arr[s.getLast()]<arr[i]){
                lr[s.pollLast()][1]=i;
            }
            //如果a[i]较小,则栈中的元素还未找到右目标值,a[i]的左目标值则为栈顶,
            if(!s.isEmpty()){
                lr[i][0]=s.getLast();
            }
            s.add(i);//该元素入栈
        }
        return lr;
    }
    //寻找左右最近的<a[i]或<=a[i]的目标索引
    public static int[][] nearLess(long[] arr){
        int n=arr.length;
        int[][] lr=new int[n][2];
        for (int i = 0; i < n; i++) {
            lr[i][0]=-1;lr[i][1]=n;
        }
        Deque<Integer> s=new ArrayDeque<>();//递增栈
        for (int i = 0; i < n; i++) {
            //如果a[i]较小,则栈中>a[i]的元素的右目标值即为a[i],这些元素出栈
            while(!s.isEmpty()&&arr[s.getLast()]>arr[i]){
                lr[s.pollLast()][1]=i;
            }
            //如果a[i]较大,则栈中的元素还未找到右目标值,a[i]的左目标值则为栈顶,
            if(!s.isEmpty()){
                lr[i][0]=s.getLast();
            }
            s.add(i);//该元素入栈
        }
        return lr;
    }
    //寻找数组每个区间大小为k的最值索引
    public static int[][] intervalPeak(long[] arr,int k){
        int n=arr.length;
        int[][] peak=new int[n][2];
        Deque<Integer> dec=new ArrayDeque<>();//递减队列
        Deque<Integer> inc=new ArrayDeque<>();//递增队列
        //将前k个元素先入队
        for (int i = 0; i < n; i++) {
            //如果队首在当前区间左边,则需要出队
            if(!dec.isEmpty()&&dec.getFirst()<i-k+1) dec.poll();
            if(!inc.isEmpty()&&inc.getFirst()<i-k+1) inc.poll();
            //添加下一个元素,队列中记录可能成为后面区间最值的索引
            while(!dec.isEmpty()&&arr[dec.getLast()]<arr[i])
                dec.pollLast();
            dec.add(i);
            while(!inc.isEmpty()&&arr[inc.getLast()]>arr[i])
                inc.pollLast();
            inc.add(i);
            //队首为区间最值,若区间不足k个则从0开始
            peak[i][0]=dec.getFirst();
            peak[i][1]=inc.getFirst();
        }
        return peak;
    }
}
